package com.gs.coursera.algorithms.core.greedy;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;

public class IntegralKnapsack {

	private final int W;
	private int n;
	private int[] v;
	private int[] w;

	public IntegralKnapsack(int capacity, int itemCount) {
		this.W = capacity;
		this.n = itemCount;
		v = new int[itemCount];
		w = new int[itemCount];
	}

	public int getCapacity() {
		return W;
	}

	public int getItemCount() {
		return n;
	}

	public void addItem(int i, int vi, int wi) {
		v[i] = vi;
		w[i] = wi;
	}

	public long solve() {

		long[][] a = new long[n + 1][W + 1];
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				a[i][j] = 0;
			}
		}

		for (int j = 0; j <= W; j++) {
			for (int i = 1; i <= n; i++) {
				if (j >= w[i - 1]) {
					a[i][j] = Math.max(a[i - 1][j], a[i - 1][j - w[i - 1]]
							+ v[i - 1]);
				} else {
					a[i][j] = a[i - 1][j];
				}
			}
		}

		return a[n][W];
	}

	/**
	 * <h3>It Works!!!</h3>
	 * 
	 * <p>
	 * In many dynamic programming problems, you will build up a 2D table row by
	 * row where each row only depends on the row that immediately precedes it.
	 * In the case of the 0/1 knapsack problem, the recurrence (from Wikipedia)
	 * is the following:
	 * </p>
	 * 
	 * <blockquote>
	 * <p>
	 * m[i, w] = m[i - 1, w] if w<sub>i</sub> > w
	 * </p>
	 * 
	 * <p>
	 * m[i, w] = max(m[i - 1, w], m[i - 1, w - w<sub>i</sub>] + v<sub>i</sub>)
	 * otherwise
	 * </p>
	 * </blockquote>
	 * 
	 * 
	 * <p>
	 * Notice that all reads from the table when filling row i only come from
	 * row i - 1; the earlier rows in the table aren't actually used.
	 * Consequently, you could save space in the 2D table by only storing two
	 * rows - the immediately previous row and the row you're filling in. You
	 * can further optimize this down to just one row by being a bit more clever
	 * about how you fill in the table entries. This reduces the space usage
	 * from O(nW) (O(n) rows and O(W) columns) to O(W) (one or two rows and O(W)
	 * columns).
	 * </p>
	 * 
	 * <p>
	 * This comes at a cost, though. Many DP algorithms don't explicitly compute
	 * solutions as they go, but instead fill in the table, then do a second
	 * pass over the table at the end to recover the optimal answer. If you only
	 * store one row, then you will get the <em>value</em> of the optimal
	 * answer, but you might not know what that optimal answer happens to be. In
	 * this case, you could read off the maximum value that you can fit into the
	 * knapsack, but you won't necessarily be able to recover what you're
	 * supposed to do in order to achieve that value.
	 * </p>
	 * 
	 * 
	 * @return
	 */
	public long solveSpace() {

		long[][] a = new long[2][W + 1];
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				a[i][j] = 0;
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= W; j++) {
				if (j >= w[i - 1]) {
					a[1][j] = Math.max(a[0][j], a[0][j - w[i - 1]] + v[i - 1]);
				} else {
					a[1][j] = a[0][j];
				}
			}
			for (int k = 0; k <= W; k++) {
				a[0][k] = a[1][k];
				a[1][k] = 0;
			}
		}

		return a[0][W];
	}

	public long solveHash() {

		Hashtable<Position, Integer> table = new Hashtable<Position, Integer>();
		/*
		 * for(int i=0; i<=n; i++){ for (int j = 0; j <= W; j++) { Position p =
		 * new Position(i, j); table.put(p, 0); } }
		 */

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= W; j++) {
				if (j >= w[i - 1]) {
					// position a[i][j]
					Position pA = new Position(i, j);
					// position a[i-1][ j]
					Position pB = new Position(i - 1, j);
					// position a[i-1][ j-w[i-1]]
					Position pC = new Position(i - 1, j - w[i - 1]);

					// a[i][j] = Math.max(a[i-1][ j], a[i-1][ j-w[i-1]] +
					// v[i-1]);
					// value of a[i-1][ j]
					Integer sB = table.get(pB);
					if (null == sB)
						sB = 0;

					// value of a[i-1][ j-w[i-1]]
					Integer sC = table.get(pC);
					if (null == sC)
						sC = 0;
					sC = sC + v[i - 1];
					if (Math.max(sB, sC) != 0)
						table.put(pA, Math.max(sB, sC));

				} else {
					// position a[i][j]
					Position pA = new Position(i, j);
					// position a[i-1][ j]
					Position pB = new Position(i - 1, j);
					// value of a[i-1][ j]
					Integer sB = table.get(pB);
					if (null != sB)
						table.put(pA, sB);

				}
			}
		}
		Position pN = new Position(n, W);
		return table.get(pN);// a[n][W];
	}

	public Long solveBig() {

		List<List<Long>> a = new ArrayList<List<Long>>();
		for (int i = 0; i <= n; i++) {
			List<Long> aj = new ArrayList<Long>();
			for (int j = 0; j <= W; j++) {
				aj.add(0L);
			}
			a.add(aj);
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= W; j++) {
				if (j >= w[i - 1]) {
					a.get(i).set(
							j,
							Math.max(a.get(i - 1).get(j),
									a.get(i - 1).get(j - w[i - 1]) + v[i - 1]));
				} else {
					a.get(i).set(j, a.get(i - 1).get(j));
				}
			}
		}

		return a.get(n).get(W);
	}

	public int solveRec(int i, int W) {
		if (i < 0) {
			return 0;
		}
		if (w[i] > W) {
			return solveRec(i - 1, W);
		} else {
			return Math.max(solveRec(i - 1, W), solveRec(i - 1, W - w[i])
					+ v[i]);
		}
	}

	public static IntegralKnapsack buildIntegerKnapsack(String fileName) {
		try {
			BufferedReader reader = null;
			try {
				reader = new BufferedReader(new FileReader(fileName));
				String line = reader.readLine();
				String[] values = line.split(" ");
				int capacity = Integer.parseInt(values[0].trim());
				int count = Integer.parseInt(values[1].trim());
				IntegralKnapsack knapsack = new IntegralKnapsack(capacity,
						count);
				int i = 0;
				while ((line = reader.readLine()) != null) {
					values = line.split(" ");
					// value
					int vi = Integer.parseInt(values[0].trim());
					// weight
					int wi = Integer.parseInt(values[1].trim());
					knapsack.addItem(i, vi, wi);
					i++;
				}
				return knapsack;
			} finally {
				if (null != reader)
					reader.close();
			}

		} catch (Exception e) {
			e.printStackTrace();
		}

		return null;
	}

}

class Position {
	private int i, j;

	public Position() {
		i = 0;
		j = 0;
	}

	public Position(int i, int j) {
		this.i = i;
		this.j = j;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + i;
		result = prime * result + j;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Position other = (Position) obj;
		if (i != other.i)
			return false;
		if (j != other.j)
			return false;
		return true;
	}

}
